package com.company.ljh.easy;

/**
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 *
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 *
 * 进阶：
 *
 * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
 */
public class 判断子序列 {
    //贪心，双指针
    public boolean isSubsequence2(String s, String t) {
        int shortIndex = 0;
        int longIndex = 0;
        if( s.length() == 0){
            return true;
        }
        while(longIndex < t.length() ){
            if(s.charAt(shortIndex) == t.charAt(longIndex)){
                shortIndex++;
            }
            longIndex++;
            if(shortIndex >= s.length()){
                return true;
            }
        }
        return false;
    }
    //动态规划，先对长字符串进行预处理，使用dp[i][j]当前位置i的下一个字符j（j为26个小写字母）的第一次出现的位置，因此在匹配时可以直接跳到下一个需要的字符的位置。
    //状态转换方程为 dp[i][j] = i 如果当前位置i的字符就等于j，或者dp[i+1][j]，代表下一个位置字符j出现的位置
    //从后往前递推生成dp[i][j]，找不到字符，置为-1
    public boolean isSubsequence(String s, String t) {
        //对字符串t进行预处理
        int dp[][] = new int[t.length()][26] ;
        for(int i=t.length()-1;i>=0;i--){
            for(int n =0;n < 26;n++){
                if(t.charAt(i) == n+'a'){
                    dp[i][n] = i;
                }else{
                    if(i >= t.length()-1){
                        dp[i][n] = -1;
                    }else{
                        dp[i][n] = dp[i+1][n];
                    }
                }
            }
        }
        int i =0;
        for(char c:s.toCharArray()){
            if(i >= t.length() || dp[i][c-'a'] == -1){
                return false;
            }else{
                //+1 因为当前字符已经被匹配被使用。
                i = dp[i][c-'a']+1;
            }
        }
        return true;
    }
}
